package gold.contest;

import gold.utils.InputUtil;

import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
import java.util.*;
import java.util.TreeMap;
import java.util.stream.Collectors;

/**
 * Created by fanzhenyu02 on 2021/12/10.
 * common problem solver template.
 */
public class LC6127 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        public long countExcellentPairs(int[] nums, int k) {
            // bitCnt[i]表示二进制中有i个数位为1的num个数
            // 0-32
            int[] bitCnt = new int[33];
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                //去重
                if (!set.add(num)) {
                    continue;
                }
                ++bitCnt[Integer.bitCount(num)];
            }

            long ans = 0;
            for (int i = 0; i <= 32; i++) {
                for (int j = Math.max(0, k - i); j <= 32; j++) {
                    ans += bitCnt[i] * bitCnt[j];
                }
            }

            return ans;
        }
    }


    class Solution_WA {
        public long countExcellentPairs(int[] nums, int k) {
            long ans = 0;
            Map<Integer, Set<Integer>> cntMap = new HashMap<>();

            for (int i = nums.length - 1; i >= 0; i--) {
                final int bitCount = bitCount(nums[i]);
                if (!cntMap.containsKey(bitCount)) cntMap.put(bitCount, new HashSet<>());
                cntMap.get(bitCount).add(nums[i]);
            }

            for (Integer cnt : cntMap.keySet()) {
                int next = Math.max(0, k - cnt);
                for (Integer nextKey : cntMap.keySet()) {
                    if (nextKey >= next) {
                        ans += cntMap.get(cnt).size() * cntMap.get(nextKey).size();
                    }
                }
            }

            return ans;
        }

        public int bitCount(int n) {
            int c = 0; // 计数器
            while (n > 0) {
                if ((n & 1) == 1) // 当前位是1
                    ++c; // 计数器加1
                n >>= 1; // 移位
            }
            return c;
        }
    }

    public void run() {
        System.out.println(new Solution_WA().countExcellentPairs(InputUtil.toIntegerArray("[1,2,3,1]"), 3));
        System.out.println(new Solution_WA().countExcellentPairs(InputUtil.toIntegerArray("[5,1,1]"), 10));

        System.out.println(new Solution().countExcellentPairs(InputUtil.toIntegerArray("[950871082,175767153,70490194,401469224,120886141,35087256,483093188,987327955,208513229,138480600,900048850,486855772,978744867,686292890,604743244,106458609,383227559,533359013,258992186,157095534]"), 34));
        System.out.println(new Solution_WA().countExcellentPairs(InputUtil.toIntegerArray("[950871082,175767153,70490194,401469224,120886141,35087256,483093188,987327955,208513229,138480600,900048850,486855772,978744867,686292890,604743244,106458609,383227559,533359013,258992186,157095534]"), 34));
    }

    public static void main(String[] args) throws Exception {
        LC6127 an = new LC6127();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
